Embodiments of the invention relate generally to an encoding process and more particularly to a method and apparatus to generate Gray code for any even count value to enable efficient pointer exchange mechanisms in asynchronous First In First Out (FIFO) buffers.
In hardware devices requiring data transfer between multiple clock domains, First In First Out (FIFO) buffers are often used to store and retrieve data. This is accomplished by writing the incoming data from one clock domain in the FIFO and then retrieving the data from the other clock domain. In addition to the data transfer across the clock domain boundary, write and read pointers of the FIFO are communicated across these domains to flag FIFO full and empty conditions, as well as other conditions.
A common problem in sending signals across clock domain boundaries is metastablility. Metastability exists when a signal is transitioning between states at the same time it is being sampled. The sampling device expects one of either two states and is not configured to correctly interpret the transitioning signal. Metastability is always a design concern in asynchronous environments.
To minimize metastablility and other error conditions, the FIFO write pointer and read pointer is encoded in Gray code before transmission to the other clock domain. This is done because of the adjacency principle between two successive Gray code values. This is true even when the pointer wraps around, i.e. while going from 7 (Gray code 100) to 0 (Gray code 000) there is only 1 bit change.
The benefits of Gray code counting techniques have long been recognized. Gray code can be described as an encoding of numbers resulting in any two adjacent numbers only differing by one digit. Ascending or descending through a Gray code sequence of numbers results in exactly one digit change, by either adding a new digit or by changing only one existing digit. This is beneficial in computing environments because additional changes introduce opportunity for additional errors.
For example, the first four values of ordinary binary representation are 00, 01, 10, 11. The change from the second number, 01, to the third number, 10, results in 2 digit changes. The 1""s placeholder goes from 1 to 0, and the 2""s placeholder goes from 0 to 1. These types of changes, as stated above, provide opportunity for error introduction in electromagnetic signaling systems.
The first four values of Gray code representation are 00, 01, 11, and 10. As can be seen in this representation, exactly one digit change exists for each adjacent Gray code representation. This is commonly called the adjacency principle. For any counting sequence, Gray code representation therefore substantially decreases opportunity for error introduction.
One disadvantage to the Gray code counting technique is that it only works when counting a number of values that is a power of 2, e.g. 2 values, 4 values, 8 values, 16 values, etc. For instance, if the same code was used to count 6 values (from 0 to 5), the moment the pointer wrapped around from 5 (Gray code 111) to 0 (Grey Code 000), there would be a 3 bit change. Therefore, the adjaceney principle of Gray code is currently only utilized when the range is a power of 2. This is a common problem in all FIFO""s whose depth is not a power of 2.